18.2 KB · ⇊ 6 parts · ⤓ Micron 18.2 KB · ⤓ HTML 26.1 KB

top

La mwbwcompressione dati senza perdita (o mwcacompressione dati mwcqlossless), in mwcginformatica e mwcwtelecomunicazioni, è una classe di mwdaalgoritmi di mwdqcompressione dati che non porta alla perdita di alcuna parte dell'mwdginformazione originale durante la fase di compressione/decompressione dei mwdwdati stessi.

Un esempio di questo tipo di compressione è dato dai formati mweqZip, mwegGzip, mwewBzip2, mwfaRar, mwfq7z. I file per cui non è accettabile una perdita di informazione, come i testi o i programmi, utilizzano questo metodo. Per le immagini fotografiche generalmente non si usano algoritmi mwfglossless in quanto sarebbero veramente poco efficienti, ma per le immagini che contengano ampie aree con colori puri spesso la compressione "senza perdita" non solo è applicabile, ma anche conveniente (mwfwGIF, mwgaPNG, MNG, mwggTIFF con compressione LZW, ZIP o RLE).

• Problemi della compressione senza perdita

• Qualità della compressione e velocità

• Tecniche di compressione

• Programmi generici per la compressione

• Formati ed algoritmi

• Audio

• Galleria d'immagini

• Video

• Voci correlate

• Collegamenti esterni

Gli algoritmi di compressione mwhglossless non possono sempre garantire che ogni insieme di dati in input diminuisca di dimensione. In altre parole per ogni algoritmo lossless ci saranno particolari dati in input che non diminuiranno di dimensione quando elaborati dall'algoritmo. Questo è facilmente verificabile con della matematica elementare:

• Si assuma che ogni file sia rappresentato da una stringa di bit di lunghezza arbitraria.

• Si supponga (per assurdo) che esista un algoritmo di compressione che trasformi ogni file in un file più corto distinto (se i file risultanti non sono distinti, l'algoritmo non può essere reversibile senza perdita di dati).

• Si considerino l'insieme dei file con lunghezza massima di mwiwN bit. Questo set ha mwja1 + 2 + 4 + ... + 2mwjqN = 2mwjgN+1-1 elementi, se si include il file di lunghezza zero.

• Ora considerando l'insieme dei file con mwkaN-1 bit, vi sono mwkq1 + 2 + 4 + ... + 2mwkgN-1 = 2mwkwN-1 file che vi appartengono, sempre considerando anche il file di lunghezza zero.

• Tale numero di elementi è più piccolo di mwlq2mwlgN+1-1. Non è possibile collegare in modo univoco gli elementi di un insieme più grande (i file da comprimere) con gli elementi di un insieme più piccolo (i file dopo la compressione).

• Questa contraddizione implica che l'ipotesi originale (che un algoritmo di compressione renda tutti i file più piccoli) sia errata.

Si può notare che la differenza di dimensione è così elevata che non fa alcuna differenza se si considerano file di dimensione esattamente mwmqN come insieme dei file da comprimere: tale insieme è comunque di dimensioni maggiori (mwmg2mwmwN) dell'insieme dei file compressi.

Una dimostrazione anche più semplice (ma equivalente) è la seguente:

1. Si assuma che ogni file sia rappresentato da una stringa di bit di lunghezza arbitraria.

2. Si supponga (per assurdo) che esista un algoritmo di compressione mwoaC che trasformi ogni file di lunghezza maggiore di 1 in un file più corto distinto (se i file risultanti non sono distinti, l'algoritmo non può essere reversibile senza perdita di dati).

3. Dato un qualunque file F di lunghezza L(F)=N, si applichi mwogC a questo file, ottenendo il file mwowC(F)

4. Si ripeta il passo precedente applicando mwpqC a mwpgC(F) e si continui in questo modo: per l'ipotesi al punto (2), si ha:

e quindi:

Dopo al massimo N iterazioni, si deve avere L(mwtgCmwtwN-1(F))=1, perché ogni iterazione deve diminuire la lunghezza di almeno un bit: questo procedimento non dipende dal valore di N. Dalle nostre ipotesi consegue quindi che esisterebbero due soli file distinti (quello contenente il bit 0 e quello contenente il bit 1). Questo è evidentemente falso, quindi l'ipotesi è falsa.

Quindi, ogni algoritmo di compressione che rende alcuni file più piccoli deve necessariamente rendere altri file più grandi o lasciarli di lunghezza invariata.

Nell'uso pratico, si considerano mwugbuoni gli algoritmi di compressione che comprimono effettivamente la maggior parte dei formati più comuni: questo non corrisponde necessariamente ad una misura di mwuwbontà in senso teorico (che misura la distanza media, misurata su tutti i file possibili, tra la lunghezza ottenuta e il numero di bit di mwvaentropia contenuti nel file, che, per un teorema di mwvqClaude Shannon, è il limite di comprimibilità teorico). Inversamente, un algoritmo teoricamente buono potrebbe non avere applicabilità pratica (ad esempio perché non riduce formati di uso comune).

In realtà, molti applicativi che utilizzano la compressione lossless prevedono di lasciare invariati gli insiemi di dati la cui dimensione sia aumentata dopo la compressione. Ovviamente, il flag che indica che questo gruppo di dati non va processato dall'algoritmo aumenta la dimensione effettiva necessaria a memorizzare il gruppo di dati stesso, ma permette di evitare un ulteriore spreco di spazio e di tempo necessario alla compressione/decompressione.

In generale, non vi è un rapporto di proporzionalità indiretta tra qualità della compressione ottenibile da un algoritmo e la sua velocità di esecuzione.

Prendiamo ad esempio la seguente stringa di dati:

La stringa richiede 48 caratteri, ma è immediatamente disponibile all'utilizzo. Un algoritmo di compressione lossless potrebbe essere "cifra-numero di ripetizioni". La stringa, utilizzando questo algoritmo, diviene quindi:

È chiaro che i dati non sono più direttamente disponibili ma occorre svolgere un passaggio intermedio (decompressione).

Poiché, dato uno stesso archivio dati, la decompressione è solitamente molto più frequente della compressione molti algoritmi sono fortemente asimmetrici: il tempo richiesto per la compressione è sostanzialmente superiore a quello richiesto per la decompressione. Questo accade anche nei riguardi delle richieste di memoria e di capacità di calcolo.

Esistono diversi algoritmi di compressione. Tra i più noti:

• mwywCodifica di Huffman

• mwzqCodifica aritmetica (o "compressione aritmetica")

• mwzwLempel-Ziv-Welch (LZW)

• mwaqLZ77

• mwawLZ78

• mwbqLZMA

• mwbwDeflate - tecnica mista: mwcaLZ77 e Huffman

• mwcgPrediction by Partial Matching (PPM)

• mwdaTrasformata di Burrows-Wheeler - (BWT)

Tra i tanti programmi di compressione molti usano un algoritmo tra quelli elencati sopra, mentre alcuni ne hanno uno proprio:

• mweqArj - algoritmo proprio

• mwewGzip - usa mwfaDeflate

• mwfgPKZIP - usa mwfwDeflate

• mwgqWinZip - usa mwggDeflate

• mwhaWinRar - algoritmo proprio

• mwhgBzip2 - usa la mwhwtrasformata di Burrows-Wheeler

• mwiq7-Zip - usa mwigLZMA

• Bandizip: freeware, compressione mwjqmulti-core e autoregolazione del rapporto compressìvo.

Supportano tutti la cifratura con algoritmo mwjwAES-128 o AES-256.

In ogni caso è possibile cifrare e comprimere il file con due programmi diversi, ma ciò rallenta l'apertura e chiusura, rispetto ad un unico programma che faccia entrambe le cose.

• mwlqApple Lossless - ALAC (Apple Lossless Audio Codec)

• mwlwDirect Stream Transfer - DST

• mwmqFLAC - Free Lossless Audio Codec

• Lossless Audio (LA) (il miglior rapporto di compressione)

• mwnqMeridian Lossless Packing - MLP

• APE mwnwMonkey's Audio

• mwoqRealPlayer - RealAudio Lossless

• Shorten - SHN

• TTA - True Audio Lossless

• WavPack - WavPack lossless

• mwpwWMA - comprende anche una variante lossless

• ABO - Adaptive Binary Optimization

• mwrqGIF - mwrgLempel-Ziv-Welch (LZW) per immagini da 2 a 256 colori

• mwsaHD Photo - Contempla un metodo di compressione lossless

• ILBM – Compressione RLE lossless per immagini mwswIFF dei computer mwtaAmiga

• mwtgJPEG - comprende una variante lossless JPEG-LS (poco utilizzata)

• mwuqJPEG 2000 - comprende un metodo di compressione lossless

• JBIG2 - comprende una compressione lossless di immagini in mwvabianco e nero

• mwvgOptiPNG - Metodo di compressione lossless in formato PNG

• mwwaPNG Portable Network Graphics - usa una variante di mwwqDeflate

• Qbit Lossless Codec - Dedicato alla compressione intra-frame

• mwxqRLE Run-length encoding algoritmo usato nei formati mwxgTGA, mwxwBMP, mwyaTIFF

• mwygFAX Gruppo 3 (1D) e Gruppo 4 (2D) - algoritmo per immagini mwywbianco e nero usato dai mwzaFAX e dal formato mwzqTIFF

• mwzwTIFF (Tagged Image File Format) - permette di scegliere tra diversi algoritmi sia lossless (tra cui mw0aLZW e mw0qRLE) o lossy (mw0gJPEG)

• WMPhoto - Contempla un metodo di compressione lossless

• mw2aHuffyuv mw2q mw2gArchiviato il 7 novembre 2005 in Internet Archive.

• CorePNG mw3g

• MSU Lossless Video Codec mw4q

• Sheervideo mw5a

• LCL mw5w

• Qbit Lossless Codec mw6g

• Animation codec

• Lagarith mw7w

• Motion mw8qJPEG2000 comprende anche una variante lossless

• mw9qCalgary corpus

• mw9wCompressione dati lossy

• mw-qCompressione dati

• mw-wCodificazione entropica

• mw-wHistory of Lossless Data Compression Algorithms in IEEE Global History Network